---

Practical and Efficient Point Insertion Scheduling Method for Parallel Guaranteed Quality Delaunay Refinement

 

Andrey Chernikov and Nikos Chrisochoides.

 

Published in 18^th ACM International Conference on Supercomputing, pages 48 -- 57, Saint-Malo, France, June, 2004

 

Abstract

 

We describe a parallel scheduler, for guaranteed quality parallel mesh generation and refinement methods. We prove a sufficient condition for the new points to be independent, which permits the concurrent insertion of more than two points without destroying the conformity and Delaunay properties of the mesh. The scheduling technique we present is much more efficient than existing coloring methods and thus it is suitable for practical use. The condition for concurrent point insertion is based on the comparison of the distance between the candidate points against the upper bound on triangle circumradius in the mesh. Our experimental data show that the scheduler introduces a small overhead (in the order of 1--2% of the total execution time) it requires local and structured communication compared to irregular, variable and unpredictable communication of the other existing practical parallel guaranteed quality mesh generation and refinement method. Finally, on a cluster of more than 100 workstations using a simple (block) decomposition our data show that we can generate about 900 million elements in less than 300 seconds.